package com.wxg.algorithm.chapter02.comparable;

import com.wxg.algorithm.chapter02.util.SortTestHelper;
import com.wxg.algorithm.common.ISort;

/**
 * 插入排序 V2
 *
 * @param <T>
 */
public class InsertionSortV2<T extends Comparable> implements ISort<T> {
    @Override
    public void sort(T[] arr) {
        for(int i=1; i<arr.length; i++){
            T e = arr[i]; // 将 i 位置的元素保存在 e 中。
            int j ; // 保存元素 e 应该插入的位置
            for(j=i; j>0; j--){
//                if(arr[j-1].compareTo(arr[j]) > 0){
                if(arr[j-1].compareTo( e ) > 0){
                    arr[j] = arr[j-1];
                }else{
                    break;
                }
            }
            arr[j] = e; // 这里 不可以直接写 arr[j] = arr[i];
        }
    }

    /**
     * 对 arr[l...r]范围的数组进行插入排序 (优化归并排序时,有用到)
     *
     * @param arr
     * @param l
     * @param r
     */
    public void sort(T[] arr, int l, int r){
        for(int i = l+1; i<=r; i++){
            T e = arr[i];
            int j;
            for(j = i; j>l; j--){
                if(arr[j-1].compareTo( e ) > 0){
                    arr[j] = arr[j-1];
                }else{
                    break;
                }
            }
            arr[j] = e;
        }
    }

    public static void main(String[] args) {
        InsertionSortV2<Integer> is = new InsertionSortV2<>();
        SelectionSort<Integer> ss = new SelectionSort<>();

        int n = 10000;

//        Integer[] intArr = SortTestHelper.generateRandomArray(n, 0, 3);
//        Integer[] intArr02 = SortTestHelper.copyIntArray(intArr);
//
//        SortTestHelper.testSort(ss, intArr02);
//        SortTestHelper.testSort(is, intArr);

        // 对近乎有序数组, "插入排序"要远远优于"选择排序"
        Integer[] intArr03 = SortTestHelper.generateNearlyOrderedArray(n, 10);
        Integer[] intArr04 = SortTestHelper.copyIntArray(intArr03);

        SortTestHelper.testSort(is, intArr03);
        SortTestHelper.testSort(ss, intArr04);

    }
}
